/*
 * @lc app=leetcode.cn id=732 lang=cpp
 *
 * [732] 我的日程安排表 III
 */
#include "include.h"
// @lc code=start
class MyCalendarThree {
public:
    MyCalendarThree() {

    }
    
    int book(int startTime, int endTime) {
        int maxBook = 0;
        int accumulateBook = 0;
        bookCounter_[startTime]++;
        bookCounter_[endTime]--;
        
        // remove useless operation (diff = 0)
        auto iter = bookCounter_.find(startTime);
        if (iter->second == 0){bookCounter_.erase(iter);}
        iter = bookCounter_.find(endTime);
        if (iter->second == 0){bookCounter_.erase(iter);}

        // 只需要找全range最大值
        // c++ 17
        for (auto &[_, freq] : bookCounter_) {
            accumulateBook += freq;
            maxBook = max(accumulateBook, maxBook);
        }
        return maxBook;
    }
private:
    // 如果要知道某个值所处位置的value

    // __|------|__
    // [start, end)
    // 范围不包含end，在end触发下降沿操作-1
    // 这时直接累加到end的-1就可在end处得到0，end值不在range里

    // __|------------|__
    // [start, end] end+1
    // 如果查询值均为int，似乎可以直接用[start, end+1)更新全range操作
    // 这时直接累加到end，还没有end+1的-1，在end处得到1，end值在range里
    
    // <start or end index, diff operation>
    map<int, int> bookCounter_;
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(startTime,endTime);
 */
// @lc code=end

// ["MyCalendarThree","book","book","book","book","book","book"]\n[[],[10,20],[20,30],[10,30],[30,40],[40,50],[20,50]]
